//: [Previous](@previous)

/*:
 ### leetcode上第283号问题：Move Zeros
 https://leetcode.com/problems/move-zeroes/
 ```
 给定一个数组nums，写一个函数，将数组中所有的0挪到数组的末尾，⽽维持其他所有非0元素的相对位置。
 举例: nums = [0, 3, 0, 1, 12]，函数运⾏后结果为[3, 1, 12, 0, 0]
 ```
 */

import Foundation

// 1. 循环遍历
// 时间复杂度 O(n^2)
// 空间复杂度 O(1)
func moveZeroes() {
    var nums = [0, 3, 0, 1, 12]
    for index in 0..<nums.count-1 {
        if nums[index] != 0 {
            continue
        }
        
        for index2 in index+1..<nums.count {
            if nums[index2] != 0 {
                nums.swapAt(index, index2)
                break
            } else {
                continue
            }
        }
    }
    print("1. \(nums)", terminator: "\n\n")
}
moveZeroes()

// 2. 将不是0的元素取出放入新数组 最后添0
// 先删除0再添加0
// 时间复杂度O(n)
// 控件复杂度O(n)
func moveZeroes2() {
    let nums = [0, 3, 0, 1, 12]
    var numstemp = [Int]()
    for num in nums {
        if num != 0 {
            numstemp.append(num)
        }
    }
    
    for _ in numstemp.count..<nums.count {
        numstemp.append(0)
    }
    
    print("2. \(numstemp)", terminator: "\n\n")
}
moveZeroes2()

// 3. 循环遍历，不是0则移动到第k(k递增)个，最后补0
// 时间复杂度 O(n)
// 空间复杂度 O(1)
func moveZeroes3() {
    var nums = [0, 3, 0, 1, 12]
    var k = 0
    let numCount = nums.count
    for index in 0..<numCount {
        let num = nums[index]
        if num != 0 {
            nums[k] = num
            k += 1
        }
    }
    for index in k..<numCount {
        nums[index] = 0
    }
    print("3. \(nums)", terminator: "\n\n")
}
moveZeroes3()

// 4. 循环遍历，k记录0值出现位置，不是0交换k与i的位置元素，同时k++
// 时间复杂度 O(n)
// 空间复杂度 O(1)
func moveZeroes4() {
    var nums = [0, 3, 0, 1, 12]
    
    var k = 0
    for index in 0..<nums.count {
        if nums[index] != 0 {
            if k != index {
                nums.swapAt(k, index)
            }
            k += 1
            
        }
    }
    print("4. \(nums)", terminator: "\n\n")
}
moveZeroes4()

//: [Next](@next)
